public class Solution {
    public int maxProfit(int[] prices) {
/*
dp[i][0] 表示第i天持股票数0
dp[i][1] 表示第i天持股票数1

第i-1天：
1.持股票数0，不买入 ，第i天持股票数：0
2.持股票数0，买入 -price[i]，第i天持股票数：1
3.持股票数1，不卖出，第i天持股票数：1
4.持股票数1，卖出 +price[i]，第i天持股票数：0

  dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
  dp[i][1]=max(dp[i-1][0],dp[i-1][1]);
*/

        int n=prices.length;
        int[][] dp=new int[n][2];

        dp[0][0]=0; //第0天不持股 
        dp[0][1]=-prices[0];//第0天持股
        for(int i=1;i<n;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return Math.max(dp[n-1][0],dp[n-1][1]);
    }
}